// https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 快速选择算法求解前K个高频元素
// 2. 哈希表统计元素频率，转换为频率-数值对
// 3. 按频率降序快速选择前K个元素
// 4. 三路分区处理相同频率的元素
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <unordered_map>

class Solution 
{
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        int m = nums.size();

        unordered_map<int, int> counts;
        for (const int& num : nums)
        {
            counts[num]++;
        }

        vector<pair<int, int>> v;
        for (const auto& [num, count] : counts)
        {
            v.push_back({num, count});
        }

        srand(unsigned(time(NULL)));
        qselect(v, 0, v.size() - 1, k);

        vector<int> ret;
        for (int i = 0 ; i < k ; i++)
        {
            ret.push_back(v[i].first);
        }

        return ret;
    }

    int getRandom(vector<pair<int, int>>& v, int left, int right)
    {
        int r = rand();
        return v[r % (right - left + 1) + left].second;
    }

    void qselect(vector<pair<int, int>>& v, int left, int right, int k)
    {
        if (k == 0) return ;
        if (left >= right) return ;

        int key = getRandom(v, left, right);
        int begin = left - 1, end = right + 1, cur = left;

        while (cur < end)
        {
            if (v[cur].second < key)
            {
                swap(v[cur], v[--end]);
            }
            else if (v[cur].second == key)
            {
                cur++;
            }
            else if (v[cur].second > key)
            {
                swap(v[cur++], v[++begin]);
            }
        }

        int a = begin - left + 1, b = end - begin - 1, c = right - end + 1;
        if (k <= a) qselect(v, left, begin, k);
        else if (k <= a + b) return ;
        else qselect(v, end, right, k - a - b);
    }
};

int main()
{
    vector<int> nums1 = {1,1,1,2,2,3}, nums2 = {1,2,1,2,1,2,3,1,3,2};
    int k1 = 2, k2 = 2;

    Solution sol;

    auto v1 = sol.topKFrequent(nums1, k1);
    auto v2 = sol.topKFrequent(nums2, k2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}